Monte Carlo Simulations

What is Monte Carlo (MC) method ?

A collection of methods for statistical simulation which utilizes repeated random sampling to make numerical estimations of an unknown parameter.

Background

Buffon's needle problem

“A needle of length L is thrown in a random fashion onto a smooth table ruled with parallel lines separated by a distance of 2L. An observer records whether or not the needle intersects a ruled line. From the experiment, it is deduced that as the sample increases the probability of the needle crossing the line tends to 1/pi.”(Schuster, 1974).

After $N$ tosses, the estimate for pi is $(2N / X)$, where $X$ is the number of times the needle intersects a line

This experiment served as a precursor of Ulam's initial description of the method [1].

MC

Monte Carlo methods leverage the Law of Large Numbers:

"As the number of identically distributed, randomly generated variables increases,
their sample mean approaches their theoretical mean.”

Estimate of pi



In [1]:

    
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

n = 1000
x = np.random.rand(n,2)

inside = x[
    np.sqrt(x[:,0]**2 + x[:,1]**2) 
    < 1]
estimate = 4 * len(inside) / len(x)

print('Estimate of pi: %s' % estimate)

plt.figure(figsize=(8,8))
plt.scatter(x[:,0], x[:,1], s=3, c='red')
plt.scatter(inside[:,0],inside[:,1],s=3,c='blue')
plt.show()









    



Estimate of pi: 3.176

Estimate of pi using 1k, 10k, 100k, 1m points

As we keep playing, and as $n\rightarrow \infty$ we approach this true value, according to the strong law of large numbers:

The probability that, as the number of trials n goes to infinity, the average of the observations converges to the expected value, is equal to one.

Importance Sampling

Importance sampling is choosing a good distribution from which to simulate random variables (Anderson E. C., 1999).

It makes intuitive sense that we must obtain a sample from important regions so as to obtain accurate results. This is done by overweighing important regions within the sample, hence the name importance sampling.

Contrary to its name importance sampling is not sampling per se but rather an approximation method.

Importance sampling is a variance reduction technique that can be used in the Monte Carlo method.

If these "important" values are emphasized by sampling more frequently, then the estimator variance can be reduced.

Hence, the basic methodology in importance sampling is to choose a distribution which "encourages" the important values.

This use of "biased" distributions will result in a biased estimator if it is applied directly in the simulation.

However, the simulation outputs are weighted to correct for the use of the biased distribution, and this ensures that the new importance sampling estimator is unbiased. The weight is given by the likelihood ratio, that is, the Radon–Nikodym derivative of the true underlying distribution with respect to the biased simulation distribution.

https://www.researchgate.net/publication/316270961_A_quantitative_approach_to_behavioural_analysis_of_drivers_in_highways_using_particle_filtering

FIGURE 1: Illustration of the three stages of importance sampling, resampling, and sampling (prediction) in PF, figure from (15)

FIGURE 2: The result for estimation of the parameter T. The blue shadow denotes the distribution of particles at each time instance while the red curve is the selected particle.

https://www.researchgate.net/publication/323500193_Predictive_airframe_maintenance_strategies_using_model-based_prognostics

Figure 1. Using Monte Carlo method to predict future degradation.

Bibliography

[1]: http://people.bordeaux.inria.fr/pierre.delmoral/MetropolisUlam49.pdf



In [ ]: